/**
 * @Auther: wangliuyang
 * @Date: 2021/4/19 22:26
 * @Description:
 */
public class Solution_23 {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        return this.merge(lists, 0, lists.length - 1);
    }

    public ListNode merge(ListNode[] lists, int start, int end) {
        if (start == end) {
            return lists[start];
        }
        int mid = start + ((end - start) >> 1);
        ListNode list1 = merge(lists, start, mid);
        ListNode list2 = merge(lists, mid + 1, end);
        return mergeTwoList(list1, list2);
    }

    public ListNode mergeTwoList(ListNode list1, ListNode list2) {
        if (list1 == null || list2 == null) {
            return list1 == null ? list2 : list1;
        }
        ListNode head = new ListNode(-1);
        ListNode tail = head;
        while (list1 != null && list2 != null) {
            if (list1.val > list2.val) {
                tail.next = list2;
                list2 = list2.next;
                tail = tail.next;
            } else {
                tail.next = list1;
                list1 = list1.next;
                tail = tail.next;
            }
        }
        if (list1 == null) {
            tail.next = list2;
        }
        if (list2 == null) {
            tail.next = list1;
        }
        return head.next;
    }

}
